JZ26 二叉搜索树与双向链表

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5

import java.util.ArrayList;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();
    
    public TreeNode Convert(TreeNode pRootOfTree) {
       if (pRootOfTree == null) return null;

       traversal(pRootOfTree);
       TreeNode root = new TreeNode(0);
       TreeNode cur = root;
        for (int i = 0; i< list.size(); i++) {
            cur.right = list.get(i);
            TreeNode temp = cur;
            cur = cur.right;
            cur.left = temp;
        }
       
       root.right.left = null;
       return root.right;
    }
    
    void traversal(TreeNode node) {
        if (node == null) return;
        
        traversal(node.left); // 取得最左边的值
        list.add(node);
        traversal(node.right);
    }
}

第二次：

可以在中序遍历时交换，这样就无需额外空间存储顺序了

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    TreeNode pre = null; // 这个算是临时节点
    TreeNode head = null; // 这个基本不用动，它只在最开始取得最左边的节点
    
    // 因为是二叉搜索树，所以中序遍历就是排序后的数据
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        ConvertSub(pRootOfTree);
        return head;
    }
    // 采用中序遍历的方式修改指针
    private void ConvertSub(TreeNode root) {
        if (root == null) return;
        ConvertSub(root.left);
        if (pre == null) { // 初始化
            pre = root;
            head = root;
        } else { 
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        ConvertSub(root.right);
    }
}